package offer.day18;

import java.util.Stack;

public class No30StackIncludeMin {
    /*
     * 面试题30：包含min函数的栈
     * 题目：定义站的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。
     * 在该栈中，调用min、push、pop的时间复杂度都是O(1)
     *
     * 思路：（min函数）借助一个辅助栈，每次压栈，都将最小的元素压入辅助栈，这样就可以保证每次辅助栈的栈顶都是最小的元素。
     * 当从栈中弹出元素时，辅助栈也弹出栈顶元素。若是最小的元素从辅助栈中被弹出，那么栈顶的 新元素就是下一个最小值。
     * （push函数）每次压栈，都将最小的元素压入辅助栈    若新进栈的元素最小，则将其压入辅助栈；
     * 									若新进栈的元素不是最小的，那么再将辅助栈栈顶的元素压入辅助栈。
     * （pop函数）每次出栈，都将辅助栈的栈顶元素也出栈。
     * */
    static Stack<Integer> stack = new <Integer>Stack();

    static Stack<Integer> stack_support = new <Integer>Stack();

    public static void main(String[] args) {
        No30StackIncludeMin s = new No30StackIncludeMin();
        s.push(3);
        s.push(4);
        s.push(2);
        s.push(1);
        System.out.println(s.min());
        s.pop();
        s.pop();
        System.out.println(s.min());
        s.push(0);
        System.out.println(s.min());

    }

    public static void push(int value) {
        stack.push(value);
        if (stack_support.isEmpty() || stack_support.peek() > value) {
            stack_support.push(value);
        } else {
            stack_support.push(stack_support.peek());
        }
    }

    public static void pop() {
        if (!stack.isEmpty() && !stack_support.isEmpty()) {
            stack.pop();
            stack_support.pop();
        } else {
            return;
        }
    }

    public static int min() {
        if (!stack.isEmpty() && !stack_support.isEmpty()) {
            return stack_support.peek();
        } else {
            return -1;
        }
    }
}
